#include "platform.h"
#include "grffile.h"
#include "grfnode.h"
#include "grftreenode.h"
#include "compress.h"
#include "decode.h"
#include "libgrf.h"
#include <algorithm> // std::replace<>
#include <memory> // std::auto_ptr<>


#pragma pack(push,1)
struct grf_header
{
	char header_magic[16] __attribute__ ((__packed__)); // "Master of Magic" + 0x00
	char header_key[14] __attribute__ ((__packed__)); // 0x01 -> 0x0e, or 0x00 -> 0x00 (no crypt)
	uint32_t offset __attribute__ ((__packed__)); // offset of file table
	uint32_t seed __attribute__ ((__packed__));
	uint32_t filecount __attribute__ ((__packed__)); // Real filecount = filecount - seed - 7
	uint32_t version __attribute__ ((__packed__)); // 0x102 0x103 0x200 0xCACA
};
#pragma pack(pop)
C_ASSERT( sizeof grf_header == 46 );

#pragma pack(push,1)
struct grf_table_entry_data
{
	// file name (char + 0x00)
	uint32_t len __attribute__ ((__packed__)); // packed len
	uint32_t len_aligned __attribute__ ((__packed__)); // same, but with the alignment (?)
	uint32_t size __attribute__ ((__packed__)); // real file size (unpacked)
	uint8_t flags __attribute__ ((__packed__)); // file flags (GRF_FLAG_FILE, GRF_FLAG_MIXCRYPT, GRF_FLAG_DES)
	uint32_t pos __attribute__ ((__packed__)); // offset in the grf file (starting from after grf header)
};
#pragma pack(pop)
C_ASSERT( sizeof grf_table_entry_data == 17 );

static const unsigned char GRF_KEY_CRYPT[14]   = { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E };
static const unsigned char GRF_KEY_NOCRYPT[14] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };

// some magic constants
#define GRF_HEADER_SIZE sizeof(grf_header)
#define GRF_HEADER_MAGIC "Master of Magic"
#define GRF_FILE_OUTPUT_VERSION 0x200
#define GRF_HASH_TABLE_SIZE 10000

// values specific to directories
#define GRF_DIRECTORY_LEN 1094
#define GRF_DIRECTORY_LEN_ALIGNED 1812
#define GRF_DIRECTORY_SIZE 1372
#define GRF_DIRECTORY_OFFSET 1418


GrfFile::GrfFile(int fd, bool writemode)
{
	m_table_offset = 0;
	m_table_size = 0;
	m_version = GRF_FILE_OUTPUT_VERSION; /* default version */
	m_fd = fd;
	m_compression_level = zlib_default_level();
	m_need_save = writemode; // file should be new (flag will be unset by prv_grf_load)
	m_write_mode = writemode;
	m_first_node = NULL;
	m_fast_table = new HashTable<GrfNode>(GRF_HASH_TABLE_SIZE);
	m_root = NULL;
	m_callback = NULL;
	m_callback_etc = NULL;
}


GrfFile::~GrfFile(void)
{
	if( m_need_save )
		this->GrfFile::grf_save();

	close(m_fd);
	delete m_fast_table;
	delete m_root;
}


bool GrfFile::grf_save(void)
{
	return ( this->GrfFile::prv_grf_write_table() && this->GrfFile::prv_grf_write_header() );
}


GrfNode* GrfFile::grf_file_add(const char* filename, const void* ptr, size_t size)
{
	if( !m_write_mode ) return NULL;
	m_need_save = true;

	uint8_t* zdata = new uint8_t[size + 100];
	std::auto_ptr<uint8_t> autorelease(zdata);
	if( zdata == NULL )
		return NULL;

	uint32_t zlen = zlib_buffer_deflate(zdata, size + 100, ptr, size, m_compression_level);
	return this->GrfFile::prv_grf_file_add(filename, GRF_FLAG_FILE, size, zlen, ALIGN(zlen,4), zdata);
}


/// Rename the given file to new_name. NB: You must provide a full path inside the grf, eg: data\some_file.txt.
/// Any existing entry with the same name will be deleted. Renaming to a directory name will give unexpected results.
bool GrfFile::grf_file_rename(GrfNode* node, const char* newname)
{
	if( !m_write_mode ) return false;
	m_need_save = true;

	GrfNode* old = this->grf_get_file(newname);
	if( old != NULL ) this->grf_file_delete(old);

	if( !m_fast_table->remove(node->filename()) )
		return false;

	if( node->tree_parent != NULL )
		node->tree_parent->parent()->m_subdir->delete_(node->tree_parent->name());

	node->m_filename.assign(newname);
	m_fast_table->insert(node->filename(), node);
	if( m_root != NULL )
		m_root->prv_grf_reg_tree_node(node);

	return true;
}


/// Removes a file from the GRF.
bool GrfFile::grf_file_delete(GrfNode* node)
{
	if( !m_write_mode ) return false;
	m_need_save = true;

	GrfNode* next = node->next;
	if( node->tree_parent != NULL )
		node->tree_parent->parent()->m_subdir->delete_(node->tree_parent->name());
	m_wasted_space += node->len_aligned;
	if( !m_fast_table->delete_(node->filename()) )
		return false;
	if( m_first_node == node )
		m_first_node = next;
	return true;
}


/// Extracts the file to the provided pointer and returns the number of bytes successfully extracted.
/// Assumes that you pre-allocated enough memory by calling grf_file_get_size().
uint32_t GrfFile::grf_file_get_contents(GrfNode* node, void* outbuf)
{
	if( (node->flags & GRF_FLAG_FILE) == 0 )
		return 0; // not a file

	uint8_t* comp = new uint8_t[DES_ALIGN(node->len_aligned)];
	std::auto_ptr<uint8_t> autorelease(comp);
	if( comp == NULL )
		return 0; // alloc failed

	lseek(m_fd, node->pos + GRF_HEADER_SIZE, SEEK_SET);
	if( read(m_fd, comp, node->len_aligned) != node->len_aligned )
		return 0; // read failed

	// decrypt (if required)
	grf_decode_data(comp, node->len_aligned, node->flags, node->len);

	// decompress to outbuf...
	uint32_t count = zlib_buffer_inflate(outbuf, node->size, comp, node->len);

	return count;
}


bool GrfFile::grf_merge(GrfFile* src, uint8_t repack_type)
{
	if( !m_write_mode ) return false;

	uint32_t i = 0;
	for( GrfNode* cur = src->m_first_node; cur != NULL; cur = cur->next )
	{
		i++;

		if( m_callback != NULL )
			if( !m_callback(m_callback_etc, this, i, src->filecount(), cur->filename()) )
				break;

		uint8_t* zdata = new uint8_t[DES_ALIGN(cur->len_aligned)];
		std::auto_ptr<uint8_t> autorelease(zdata);
		if( zdata == NULL )
			return false; // alloc failed

		lseek(src->m_fd, cur->pos + GRF_HEADER_SIZE, SEEK_SET);
		if( read(src->m_fd, zdata, cur->len_aligned) != cur->len_aligned )
			return false; // read failed

		if( repack_type >= GRF_REPACK_DECRYPT )
		{
			grf_decode_data(zdata, cur->len_aligned, cur->flags, cur->len);
			cur->flags = cur->flags & ~(GRF_FLAG_MIXCRYPT | GRF_FLAG_DES);
		}
		if( repack_type >= GRF_REPACK_RECOMPRESS )
		{
			// TODO: recompress the file
		}

		this->GrfFile::prv_grf_file_add(cur->m_filename.c_str(), cur->flags, cur->size, cur->len, cur->len_aligned, zdata);
		m_need_save = true;
	}

	if( m_callback != NULL )
		m_callback(m_callback_etc, this, src->filecount(), src->filecount(), NULL);

	return true;
}


void GrfFile::grf_create_tree(void)
{
	uint32_t i=0, j=100;
	if( m_root != NULL )
		return;
	// the idea is simple : get to each file and scan them~
	// First, create the root node...
	m_root = new GrfTreeNode(true, "", NULL, NULL);
	// now, list all files in the archive...
	GrfNode* cur_node = m_first_node;
	while(cur_node != NULL) {
		// ... and register 'em
		m_root->prv_grf_reg_tree_node(cur_node);
		cur_node = cur_node->next;
		i++;
		if (--j<=0) {
			j=100;
			if( m_callback != NULL )
				m_callback(m_callback_etc, this, i, this->filecount(), cur_node->filename());
		}
	}

	if( m_callback != NULL )
		m_callback(m_callback_etc, this, this->filecount(), this->filecount(), NULL);
}


GrfNode* GrfFile::grf_get_file(const char* filename)
{
	return m_fast_table->find(filename);
}


bool GrfFile::grf_repack(uint8_t repack_type)
{
	if( !m_write_mode ) return false;

	//FIXME: 'filemem' variable potentially leaks memory

	GrfNode* node = m_first_node;
	GrfNode* prenode;
	uint32_t i=0;
	uint32_t save_pos = 0;
	if (node == NULL) return true; // nothing to do on an empty file
	switch(repack_type) {
		case GRF_REPACK_FAST: break; case GRF_REPACK_DECRYPT: break; // case GRF_REPACK_RECOMPRESS: break;
		default: return false; /* bad parameter */
	}
	while(node->next != NULL) node = node->next;
	if (m_table_offset >= (node->pos+node->len_aligned)) {
		save_pos = m_table_offset + m_table_size;
	} else {
		save_pos = node->pos+node->len_aligned;
	}
	node = m_first_node;
	// ok, let's go!
	// Save header with version "0xCACA", but keep initial version. If we save again, it means it worked!
	uint32_t old_version = m_version;
	m_version = (0xCACA | repack_type << 24); // save repack_type as well~
	this->GrfFile::grf_save();
	m_need_save = true;
	m_version = old_version;
	// First operation: enumerate files, and find a gap
	i=0;
	// first node will never get moved, so create a "pre-first" node that'll be the one who won't get to be moved
	prenode = new GrfNode;
	prenode->next = node;
	node = prenode;
	while(node != NULL) {
		GrfNode* next = node->next;
		i++;
		if (next == NULL) break; /* can't remove void at end */
		if (node->pos+node->len_aligned < next->pos) { // found a gap !
			// save position of current file at end of GRF, in case of problem while repacking~
			uint8_t* filemem;
			int p=0;
			lseek(m_fd, save_pos + GRF_HEADER_SIZE, SEEK_SET);
			write(m_fd, (void *)(&next->pos), 4);
			if( m_callback != NULL ) if( !m_callback(m_callback_etc, this, i, this->filecount(), next->filename()) ) break;
			filemem = new uint8_t[DES_ALIGN(next->len_aligned)];
			lseek(m_fd, next->pos + GRF_HEADER_SIZE, SEEK_SET);
			while( p < next->len_aligned )
				p += read(m_fd, filemem+p, next->len_aligned - p);
			// ok, we got the data :)
			if (repack_type >= GRF_REPACK_DECRYPT) {
				// we have at least to decrypt the file, if encrypted.
				grf_decode_data(filemem, next->len_aligned, next->flags, next->len);
				// clear encryption flags...
				next->flags = next->flags & ~(GRF_FLAG_MIXCRYPT | GRF_FLAG_DES);
			}
			if (repack_type >= GRF_REPACK_RECOMPRESS) {
				// NOT SUPPORTED ! (to be implemented on next release - which will be something like 0.1.22)
//				void *filenew = malloc(next->size);
//				count = zlib_buffer_inflate(filenew, next->size, filemem, next->len);
			}
			// write the file to its new localtion !
			p=0;
			next->pos = node->pos+node->len_aligned;
			lseek(m_fd, next->pos + GRF_HEADER_SIZE, SEEK_SET);
			while( p < next->len_aligned )
				p += write(m_fd, filemem+p, next->len_aligned - p);
		} else {
			bool need_write = false;
			uint8_t* filemem;
			int p;
			// no need to move file, but...
			if (repack_type >= GRF_REPACK_DECRYPT) {
				if( next->flags & (GRF_FLAG_MIXCRYPT | GRF_FLAG_DES) )
				{
					if( m_callback != NULL )
						m_callback(m_callback_etc, this, i, this->filecount(), next->filename());

					filemem = new uint8_t[DES_ALIGN(next->len_aligned)];
					p=0;
					lseek(m_fd, next->pos + GRF_HEADER_SIZE, SEEK_SET);
					while( p < next->len_aligned )
						p += read(m_fd, filemem+p, next->len_aligned - p);
					grf_decode_data(filemem, next->len_aligned, next->flags, next->len);
					next->flags = next->flags & ~(GRF_FLAG_MIXCRYPT | GRF_FLAG_DES);
					need_write = true;
				}
			}
			if (repack_type >= GRF_REPACK_RECOMPRESS) {
				//TODO
			}
			if (need_write) {
				p=0;
				lseek(m_fd, node->pos + node->len_aligned + GRF_HEADER_SIZE, SEEK_SET);
				while( p < next->len_aligned )
					p += write(m_fd, filemem+p, next->len_aligned - p);
			}
		}
		node = next;
	}
	delete prenode;
	this->GrfFile::grf_save();
	this->GrfFile::prv_grf_recount_wasted_space();
	return true;
}


GrfFile* GrfFile::grf_load_from_new(void)
{
	if( !this->GrfFile::prv_grf_load() )
		return NULL;

	return this;
}


void GrfFile::grf_set_callback(bool (*callback)(void *, GrfFile*, int, int, const char *), void* etc)
{
	m_callback = callback;
	m_callback_etc = etc;
}


GrfTreeNode* GrfFile::grf_tree_get_root(void)
{
	return m_root;
}


void GrfFile::grf_set_compression_level(int level)
{
	m_compression_level = level;
}


GrfNode* GrfFile::grf_get_file_first(void)
{
	return m_first_node;
}


uint32_t GrfFile::grf_get_file_list(GrfNode** arr, size_t num)
{
	return m_fast_table->foreach_val(arr, num);
}


uint32_t GrfFile::filecount(void) const
{
	return m_fast_table->count();
}


/// Returns the amount of data (in bytes) that would be theorically saved if the file gets repacked.
uint32_t GrfFile::wasted_space(void) const
{
	return m_wasted_space;
}


GrfFile* __cdecl GrfFile::grf_new(const char* filename, bool writemode)
{
	int flags = ( writemode ) ? O_RDWR | O_CREAT : O_RDONLY;
#ifdef _O_BINARY
	flags |= _O_BINARY;
#endif
#ifdef O_LARGEFILE
	flags |= O_LARGEFILE;
#endif

	int fd = open(filename, flags);
	return new GrfFile(fd, writemode);
}


GrfFile* __cdecl GrfFile::grf_new_by_fd(int fd, bool writemode)
{
	return new GrfFile(fd, writemode);
}


bool GrfFile::prv_grf_load(void)
{
	int result;
	int hcall = 100;
	m_wasted_space = 0;

	// load header...
	m_need_save = false;
	lseek(m_fd, 0, SEEK_SET);

	struct grf_header head;
	result = read(m_fd, &head, sizeof(head));
	if( result != sizeof(head) ) return false;

	if (strncmp(head.header_magic, GRF_HEADER_MAGIC, sizeof(head.header_magic)) != 0) return false; // bad magic !
	if( memcmp(head.header_key, GRF_KEY_CRYPT, sizeof(GRF_KEY_CRYPT)) != 0 && memcmp(head.header_key, GRF_KEY_NOCRYPT, sizeof(GRF_KEY_NOCRYPT)) != 0 ) return false;

	switch( head.version )
	{
		case 0x102: case 0x103: case 0x200: case 0xCACA: break;
		default: return false; /* unknown version */
	}

	m_table_offset = head.offset;
	uint32_t filecount = head.filecount - head.seed - 7;
	// version was set from grf_new()
//	this->version = GRF_FILE_OUTPUT_VERISON; /* do not store version as we'll save to this version anyway, unless we're repacking */

	if( filecount == 0 ) return true; // do not even bother reading file table, it's empty

	struct stat grfstat;
	if( fstat(m_fd, &grfstat) != 0 ) return false;

	int grfsize = grfstat.st_size;
	if( m_table_offset + GRF_HEADER_SIZE > grfsize ) return false;

	GrfNode* last = m_first_node; // helper pointer to speed up inserts
	if( last != NULL )
		while( last->next != NULL )
			last = last->next; // seek to end of list

	uint32_t remaining_files = filecount;

	switch( head.version )
	{
		case 0x102:
		case 0x103:
		{// old GRF files
			/// table: [ <size>.l <unknown>.w <name>.s <unknown>.l <entry>.17b ]* , strlen(name) == size - 6
			/// entry: [ <len>.l <len_aligned>.l <size>.l <flags>.b <pos>.l ].17b

			lseek(m_fd, m_table_offset + GRF_HEADER_SIZE, SEEK_SET);

			int dlen = grfsize - (m_table_offset + GRF_HEADER_SIZE);
			uint8_t* table = new uint8_t[dlen];
			std::auto_ptr<uint8_t> autorelease(table);
			if( read(m_fd, (void *)table, dlen) != dlen ) return false;
			m_wasted_space = m_table_offset;
			uint8_t* pos = table;
			uint8_t* pos_max = table + dlen;
			while( pos < pos_max )
			{
				remaining_files--;
				size_t available_data = pos_max - pos;

				int fn_len = (*(uint32_t*)pos) - (4+2);
				if( fn_len > available_data ) return false;
				pos += 4; // size
				pos += 2; // unknown field

				const char* fn_name = (char*)pos;
				pos += fn_len; // name

				pos += 4; // unknown field

				struct grf_table_entry_data tmpentry;
				memcpy(&tmpentry, pos, sizeof(tmpentry));
				pos += sizeof(tmpentry);

				if( (tmpentry.flags & GRF_FLAG_FILE) == 0 || tmpentry.size == 0 )
					continue; // do not register "directory" entries and empty(bogus) files

				uint8_t* encname = new uint8_t[DES_ALIGN(fn_len)];
				std::auto_ptr<uint8_t> autorelease(encname);
				memcpy(encname, fn_name, fn_len);
				grf_decode_filename(encname, fn_len);
				fn_name = (char*)encname;

				GrfNode* entry = new GrfNode;
				entry->m_filename.assign(fn_name, fn_len);
				entry->flags = tmpentry.flags;
				entry->size = tmpentry.size;
				entry->len = tmpentry.len-tmpentry.size-715;
				entry->len_aligned = tmpentry.len_aligned-37579;
				entry->pos = tmpentry.pos;
				entry->parent = this;
				m_wasted_space -= entry->len_aligned;

				// check file extension
				entry->flags |= ( grf_file_is_mixcrypt(entry->m_filename.c_str()) ) ? GRF_FLAG_MIXCRYPT : GRF_FLAG_DES;

				this->GrfFile::prv_linkedlist_attach(entry, last);
				last = entry; // update cursor

				m_fast_table->insert(entry->filename(), entry);

				if (--hcall<=0) {
					hcall = 100;
					if( m_callback != NULL )
						if( !m_callback(m_callback_etc, this, filecount - remaining_files, filecount, entry->filename()) )
							return false;
				}
			}
		}
		break;
		case 0x200:
		{// new GRF files
			/// table: <compsize>.l <realsize>.l [ <name>.s <entry>.17b ]*
			/// entry: [ <compsize>.l <datasize>.l <size>.l <type>.b <offset>.l ].17b

			lseek(m_fd, m_table_offset + GRF_HEADER_SIZE, SEEK_SET);

			uint32_t posinfo[2];
			if( read(m_fd, (void *)&posinfo, sizeof(posinfo)) != sizeof(posinfo) ) return false;
			if( m_table_offset + GRF_HEADER_SIZE + 8 + posinfo[0] > grfsize ) return false;

			uint8_t* table_comp = new uint8_t[posinfo[0]]; // posinfo[0] = comp size
			uint8_t* table = new uint8_t[posinfo[1]];      // posinfo[1] = decomp size
			std::auto_ptr<uint8_t> autorelease1(table_comp);
			std::auto_ptr<uint8_t> autorelease2(table);
			if( read(m_fd, table_comp, posinfo[0]) != posinfo[0] ) return false;
			if( zlib_buffer_inflate(table, posinfo[1], table_comp, posinfo[0]) != posinfo[1] ) return false;
			autorelease1.reset();

			uint8_t* pos = table;
			uint8_t* pos_max = table + posinfo[1];
			m_wasted_space = grfsize - GRF_HEADER_SIZE - 8 - posinfo[0];
			while( pos < pos_max )
			{
				remaining_files--;
				size_t available_data = pos_max - pos;

				const char* fn_name = (char*)pos; 
				int fn_len = strnlen(fn_name, available_data);
				if( fn_len + sizeof(struct grf_table_entry_data) > available_data ) return false;
				pos += fn_len + 1;

				struct grf_table_entry_data tmpentry;
				memcpy(&tmpentry, pos, sizeof(tmpentry));
				pos += sizeof(tmpentry);

				if( (tmpentry.flags & GRF_FLAG_FILE) == 0 || tmpentry.size == 0 )
					continue; // do not register "directory" entries and empty(bogus) files

				GrfNode* entry = new GrfNode;
				entry->m_filename.assign(fn_name, fn_len);
				entry->flags = tmpentry.flags;
				entry->size = tmpentry.size;
				entry->len = tmpentry.len;
				entry->len_aligned = tmpentry.len_aligned;
				entry->pos = tmpentry.pos;
				entry->parent = this;

				m_wasted_space -= tmpentry.len_aligned;
				this->GrfFile::prv_linkedlist_attach(entry, last);
				last = entry; // update cursor

				m_fast_table->insert(entry->filename(), entry);

				if (--hcall<=0) {
					hcall = 100;
					if( m_callback != NULL )
						if( !m_callback(m_callback_etc, this, filecount - remaining_files, filecount, entry->filename()) )
							return false;
				}
			}
		}
		break;
		case 0xCACA:
		{// broken-by-repack
			return false; // TODO TODO TODO TODO XXX FIXME TODO XXX FIXME
		}
		break;
		default:
			return false;
	}

	if( remaining_files != 0 ) return false;

	// sort entries using quicksort
	if( !this->GrfFile::prv_grf_quicksort() ) return false;

	// overlap check
	GrfNode *x = m_first_node;
	uint32_t prev = 0;
	while (x != NULL) {
		if (prev > x->pos+x->len_aligned) {
			m_wasted_space += x->len_aligned;
			m_fast_table->delete_(x->filename());
			x = x->next;
			continue;
		}
		prev = x->pos + x->len_aligned;
		x = x->next;
	}

	// call the callback, if any~
	if( m_callback != NULL )
		m_callback(m_callback_etc, this, this->filecount(), this->filecount(), NULL);

	return true;
}


bool GrfFile::prv_grf_write_header(void)
{
	struct grf_header file_header;
	memset(&file_header, 0, sizeof(struct grf_header));
	strncpy(file_header.header_magic, GRF_HEADER_MAGIC, sizeof(file_header.header_magic));
	memcpy(file_header.header_key, GRF_KEY_CRYPT, sizeof(GRF_KEY_CRYPT));
	file_header.offset = m_table_offset;
	file_header.filecount = this->filecount() + 7;
	file_header.version = m_version;

	lseek(m_fd, 0, SEEK_SET);
	if( write(m_fd, &file_header, sizeof(file_header)) != sizeof(file_header) )
		return false;

	m_need_save = false;
	return true;
}


bool GrfFile::prv_grf_write_table(void)
{
	// Step 1 : generate a proper table
	// We need to determine the final size of the table. It's :
	// Len of Filename + 1 + sizeof(struct grf_table_entry_data)
	uint32_t table_size=0;
	GrfNode* node = m_first_node;
	uint8_t *table, *pos;
	GrfNode* prev;

	while(node != NULL) {
		table_size += strlen(node->filename())+1+sizeof(struct grf_table_entry_data);
		node = node->next;
	}

	if (table_size == 0) {
		table = new uint8_t[1];
		*(char *)(table) = 0;
	} else {
		table = new uint8_t[table_size];
		pos=table;
		node = m_first_node;
		while(node != NULL) {
			struct grf_table_entry_data te;
			int j=strlen(node->filename());
			memcpy(pos, node->filename(), j);
			pos+=j;
			*(char *)(pos) = 0;
			pos++;
			te.len = node->len;
			te.len_aligned = node->len_aligned;
			te.size = node->size;
			te.pos = node->pos;
			te.flags = node->flags;
			memcpy(pos, (void *)&te, sizeof(struct grf_table_entry_data));
			pos+=sizeof(struct grf_table_entry_data);
			node = node->next;
		}
	}

	pos = new uint8_t[table_size + 100];
	*(uint32_t *)(pos+4) = table_size; /* initial size */

	// Compress the table using zlib
	table_size = zlib_buffer_deflate(pos+8, table_size + 100 - 8, table, table_size, m_compression_level);
	delete[] table;
	if (table_size == 0) {
		delete[] pos;
		return false;
	}
	
	*(uint32_t *)(pos) = table_size; /* compressed size */
	table_size += 8;
	m_table_size = table_size;
	/* compute new position for the table */
	prev = this->GrfFile::prv_grf_find_free_space(table_size);
	if (prev == NULL) { // no files
		m_table_offset = 0;
	} else {
		m_table_offset = prev->pos + prev->len_aligned;
	}
	lseek(m_fd, m_table_offset + GRF_HEADER_SIZE, SEEK_SET);
	if (write(m_fd, pos, table_size) != table_size) { delete[] pos; return false; }
	delete[] pos;
	if (prev == NULL) { // no file found in archive -> truncate at end of table
		ftruncate(m_fd, m_table_offset + GRF_HEADER_SIZE + table_size);
	} else if (prev->next == NULL) { // file was EOF -> truncate at end of table 
		ftruncate(m_fd, m_table_offset + GRF_HEADER_SIZE + table_size);
	} else { // some files are after us, truncate at end of last file
		uint32_t pos = 0;
		node = m_first_node;
		while(node != NULL) { // TODO: Optimize this (as we know that files are sorted, optimization is possible)
			uint32_t p=node->pos+node->len_aligned; // position of EOF
			if( pos < p )
				pos = p;
			node = node->next;
		}
		ftruncate(m_fd, pos+GRF_HEADER_SIZE);
	}
	return true;
}


/// Find first node with at least 'size' free space after it.
/// If there are no nodes, returns NULL. If there is no room, returns last node.
GrfNode* GrfFile::prv_grf_find_free_space(size_t size)
{
	if( m_first_node == NULL )
		return NULL; // special case : nothing in the grf

	GrfNode* cur;

	for( cur = m_first_node; cur->next != NULL; cur = cur->next ) 
	{
		uint32_t avail = cur->next->pos - (cur->pos + cur->len_aligned);
		if( avail >= size )
			break; //found.
	}

	return cur;
}


int grf_quicksort_sub(const void* left, const void* right)
{
	GrfNode* l = *(GrfNode**)left;
	GrfNode* r = *(GrfNode**)right;
	return ( l->pos < r->pos ) ? -1
	     : ( l->pos > r->pos ) ? +1
	     :                        0;
}


bool GrfFile::prv_grf_quicksort(void)
{
	size_t num = this->filecount();
	GrfNode** arr = new GrfNode*[num+1];
	m_fast_table->foreach_val(arr, num+1);

	qsort(arr, num, sizeof(GrfNode*), &grf_quicksort_sub);

	// restore order~
	GrfNode* piv = NULL;
	for( int i = 0; arr[i] != NULL; ++i )
	{
		arr[i]->prev = piv;
		if( piv != NULL ) piv->next = arr[i];
		piv = arr[i];
	}
	piv->next = NULL;
	m_first_node = arr[0];

	delete[] arr;
	return true;
}

void GrfFile::prv_grf_recount_wasted_space(void)
{
	struct stat s;
	if( fstat(m_fd, &s) != 0 )
		return;

	uint32_t w = s.st_size - GRF_HEADER_SIZE - m_table_size;

	GrfNode* node = m_first_node;
	while( node != NULL ) {
		w -= node->len_aligned;
		node = node->next;
	}
	m_wasted_space = w;
}

void GrfFile::prv_linkedlist_attach(GrfNode* node, GrfNode* anchor)
{
	if( anchor == NULL )
	{// prepend to the beginning of list
		if( node != m_first_node )
			node->next = m_first_node; // if we insert a new file, do some cleaning
		node->prev = NULL;
		m_first_node = node;
	}
	else
	{// append at the specified anchor node
		node->next = anchor->next;
		node->prev = anchor;
		anchor->next = node;
		if( node->next != NULL )
			node->next->prev = node;
	}
}

GrfNode* GrfFile::prv_grf_file_add(const char* filename, uint8_t flags, uint32_t real_size, uint32_t zlen, uint32_t zlen_aligned, const uint8_t* zdata)
{
	// remove previous entry, if it exists
	GrfNode* old_node = m_fast_table->find(filename);
	if( old_node != NULL ) {
		this->GrfFile::grf_file_delete(old_node);
		m_wasted_space += old_node->len_aligned;
	}

	// find a free spot in the grf archive
	GrfNode* prev = this->GrfFile::prv_grf_find_free_space(zlen_aligned);

	// prepare new entry
	GrfNode* node = new GrfNode;
	node->m_filename = filename;
	std::replace(node->m_filename.begin(), node->m_filename.end(), '/', '\\');
	node->pos = ( prev == NULL ) ? 0 : prev->pos + prev->len_aligned;
	node->size = real_size;
	node->len = zlen;
	node->len_aligned = zlen_aligned;
	node->flags = flags;
	node->parent = this;

	// write data to disk
	lseek(m_fd, node->pos + GRF_HEADER_SIZE, SEEK_SET);
	if( write(m_fd, zdata, node->len_aligned) != node->len_aligned )
		return NULL;

	// register new entry
	this->GrfFile::prv_linkedlist_attach(node, prev);
	m_fast_table->insert(node->filename(), node);
	if( m_root != NULL )
		m_root->prv_grf_reg_tree_node(node);

	if( node->next != NULL )
		m_wasted_space -= node->len_aligned;
	return node;
}
